A Label Switched Path (LSP) in Multi-Protocol Label Switching (MPLS) is set up by using a hop-by-hop routing and signaling information exchange, i.e., a label request and label mapping. During the setup of an LSP, the signaling messages for the label distribution are ensured to be transported over a loop-free path to prevent the LSP from having loops.
The Request for Comments 3063 (RFC3063) published by the Network Working Group of the Internet Society in 2001 presents a method for detecting and preventing a loop in the MPLS control plane, referred to as a colored thread method. In a network topology as illustrated in FIG. 1, an ingress node R1 initiates LSP setup to an egress node R5. For the service, i.e., a forwarding equivalence class corresponding to the LSP, R1 creates a globally unique sequence of digits identifying a path to the egress node R5. The sequence of digits is referred to as a colored thread, and the color of the thread is characterized by the value of the corresponding sequence of digits. R1 carries the sequence of digits, i.e., extends the colored thread, together with a hop count in a label request to be transmitted to a downstream node R2. This process is repeated on each of the nodes over R2→R3→R4 until arriving at R5. If the downstream node of the node R4 is changed from R5 to R8 due to some reason, for example, a configuration error or oscillation of the network topology, etc., the colored thread originated from R1 and the label request initiated from R1 finally go back to R1 via nodes R7 and R6. In this way, R1 may detect that the color of a colored thread for the service received via another interface is the same as the color of the colored thread extended downstream. This indicates the presence of a routing loop in the control plane. In this case, R1 becomes a loop-back crossing point.
When detecting the presence of the loop, R1 identifies the interface of loop-back of the colored thread to be in a stalled status. In this case, neither any colored thread nor any label request signaling for the same service, which is received at the interface in the stalled status from an upstream node, is extended downstream. In addition, R1 may create a new colored thread for the service, i.e., another colored thread with a different color, set a hop count with the maximum value (i.e., 255), and transmit downstream. The colored thread is copied onto each one of the nodes over the loop R1→R2→R3→R4→R8→R7→R6→R1, so as to identify the loop in the control plane. In this case, the hop count 255 indicates that the path, on which the colored thread is located, is a loop. The colored thread with the new color indicates the path of the loop. In this way, the setup of the LSP is stalled at the interface in the stalled status, thereby preventing the setup of an LSP having loop in the data plane.
As illustrated in FIG. 2, the flow of a rewinding process of a colored thread in existing systems includes the following steps. In Step 201: A node detects an event that a colored thread is rewound. In Step 202: The node rewinds the colored thread to all upstream neighbor nodes and distributes label mapping to all upstream neighbor nodes. In Step 203: The colors of colored threads at all local interfaces are set to transparent. In Step 204: The rewinding process of the colored thread is finished.
If the next-hop node of the node R4 is changed from the node R8 to R5, R4 transmits to R8 an instruction to withdraw the colored thread, and then R4 extends the colored thread to R5. Since R5 is the egress node of the LSP, R5 may rewind the received colored thread to its upstream node R4. The process is repeated on each of nodes over R4→R3→R2 until arriving at R1. R4 transmits to R8 an instruction to withdraw the colored thread, so that the colored thread of R4→R8 is withdrawn. The process is repeated on each of nodes over R8→R7-R6 until arriving at R1. The instruction information of rewinding colored thread is contained in a label allocation message and is transmitted upstream. The instruction information of withdrawing colored thread is carried in an MPLS LSP withdrawal message and is transmitted downstream.
As illustrated in FIG. 3, the flow of a withdrawal process of a colored thread on a node in the existing systems includes the following steps. In Step 301: A node detects an event that a colored thread is withdrawn. In Step 302: The node removes the colored thread information of the interface of the withdrawn colored thread. In Step 303: It is judged whether there is any colored thread for the same forwarding equivalence class from another upstream node, and if there is, step 305 is executed; otherwise, step 304 is executed. In Step 304: The node distributes an thread withdrawal event to the downstream neighbor node(s) and then the process proceeds to step 307. In Step 305: It is judged whether the hop counts for all upstream interfaces are less than those for downstream interfaces and less than 255, and if so, step 306 is executed; otherwise, step 307 is executed. In Step 306: The colored thread is extended to the downstream neighbor node. In Step 307: The withdrawal process of the colored thread is finished.
If the colored thread rewinding message arrives at R1 earlier than the colored thread withdrawal message, R1 continues to rewind the colored thread to R6. The process is also repeated on each of the nodes over R6→R7→R8 until arriving at a node which has finished the withdrawal process. Without loss of generality, R7 is assumed as the node which has finished the withdrawal process. In this way, at least a redundant LSP segment in the data plane, i.e., R7→R6→R1, is generated. This redundant and undesirable LSP segment has to be removed, from whichever of the perspective of utilization of network resources and that of controlled transmission of data services.
Normally, when a colored thread rewinding message arrives at the node R7, since there is no upstream node on the label request path of R7, R7 triggers a label release message and transmits the label release message to R6, and withdraws the colored thread. The process is repeated on R6 until arriving at R1. Since R1 is the starting point of the LSP, the transmission of the label release message is terminated on R1. In this way, the redundant LSP segment is removed.
The inventor discovered during research and application that the existing systems have at least the following disadvantages.
Firstly, if a node capable of processing an Equal Cost Multiple Path (ECMP) is on a loop-back path, there is a risk of generating a loop-back LSP. As illustrated in FIG. 4, it is assumed that each of the first ingress node R1 and the second ingress node R6 initiates LSP setup to egress node R5, that is, initiates the setup of a Multi-Point-to-Point (MP2P) LSP, and node R3 supports ECMP. In the direction toward R5, the downstream node of the node R3 is R4, the downstream node of R7 is R8, the downstream node of R8 is R3, and the downstream node of R4 is R5. If the node R7 becomes a downstream node of the ECMP supporting node R3 in the direction toward R5 and the downstream node of the node R4 is changed from R5 to R9 due to some reason, for example, a configuration error or oscillation of the network topology, etc., a colored thread extended from R1 is merged at R8 with a colored thread extended from R6. The colored thread extended from R6 arrives at R8 earlier, undergoes an ECMP processing on the node R3 and goes back to R7, and the colored thread extended from R1 arrives at R8 subsequently and is changed in color at R8 as specified in the RFC3063, that is, a colored thread is extended from R8, arrives at R4 via R3 and is looped back to R8.
In addition, if the downstream node of R4 is changed from R9 back to R5, R4 distributes a colored thread withdrawal message to R9 and continues to extend the colored thread to R5. R5 distributes a colored thread rewinding message to R4. If the colored thread rewinding message arrives at the node R8 earlier than the colored thread withdrawal message, the redundant LSP segment R8→R9 is removed, but the redundant LSP segment R7→R3 cannot be removed. In this way, a loop-back LSP of R3→R8→R7→R3 is set up, resulting in two desirable LSPs, i.e., R1→R2→R3→R4→R5 and R6→R7→R8→R3→R4→R5, and one undesirable LSP loop, i.e., R1→R2→R3→R7→R8→R3.